/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    	ListNode* cur = NULL;
		ListNode* head = NULL;

		while (l1 || l2) {
			if (l2 == NULL || (l1 != NULL && l1->val < l2->val)) {
				if (head == NULL) {
					head = l1;
					cur = l1;
				} else {
					cur->next = l1;
					cur = cur->next;
				}
				l1 = l1->next;
			} else {
				if (head == NULL) {
					head = l2;
					cur = l2;
				} else {
					cur->next = l2;
					cur = cur->next;
				}
				l2 = l2->next;
			}
		}
		return head;

    }
};